#include "mySearch.h"
#include <iostream>
#include <string>
#include <stack>

using namespace std;

SSTable::SSTable()
{
	length = 0;
	origin = NULL;
}

SSTable::SSTable(int length,int* origin)
{
	this->length = length;
	this->origin = origin;
}

SSTable::~SSTable()
{
	;
}

int SSTable::getLength()
{
	return length;
}

int* SSTable::getOrigin()
{
	return origin;
}

void SSTable::setLength(int length)
{
	this->length = length;
}

void SSTable::setOrigin(int* origin)
{
	this->origin = origin;
}

int SSTable::binSearch(int val)
{
	int low = 0;
	int high = length;
	int result;
	while (low <= high)
	{
		int present = (low + high) / 2;
		if (origin[present] > val)
		{
			high = present - 1;
		}
		else if (origin[present] < val)
		{
			low = present + 1;
		}
		else
		{
			result = present;
			break;
		}
	}
	if (low > high)result = -1;
	return result;
}

BSTreeNode::BSTreeNode()
{
	data = NULL;
	lchild = NULL;
	rchild = NULL;
}

BSTreeNode::BSTreeNode(int data)
{
	this->data = data;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode* lchild, BSTreeNode* rchild)
{
	this->data = data;
	this->lchild = lchild;
	this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{
	;
}

int BSTreeNode::getData()
{
	return data;
}

BSTreeNode* BSTreeNode::getLChild()
{
	return lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
	return rchild;
}

void BSTreeNode::setData(int data)
{
	this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{
	this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{
	this->rchild = rchild;
}

BSTree::BSTree()
{
	num = 0;
	root = NULL;
}

BSTree::BSTree(int num, int* data)
{
	this->num = num;
	root->setData(data[0]);
	int i = 1;
	BSTreeNode* k = new BSTreeNode;
	while (i < num)
	{
		BSTreeNode* newroot = new BSTreeNode;
		newroot = root;
		while (newroot != NULL)
		{
			if (newroot->getData() > data[i])
			{
				k = newroot;
				newroot = newroot->getLChild();
			}
			else if (newroot->getData() < data[i])
			{
				k = newroot;
				newroot = newroot->getRChild();
			}
		}
		if (k->getData() > data[i])
		{
			BSTreeNode* newroot2 = new BSTreeNode;
			newroot2->setData(data[i]);
			k->setLChild(newroot2);
		}
		else
		{
			BSTreeNode* newroot2 = new BSTreeNode;
			newroot2->setData(data[i]);
			k->setRChild(newroot2);
		}
		i++;
	}
}

BSTree::~BSTree()
{

}

int BSTree::getNum()
{
	return num;
}

BSTreeNode* BSTree::getRoot()
{
	return root;
}

void BSTree::setNum(int num)
{
	this->num = num;
}

void BSTree::setRoot(BSTreeNode* root)
{
	this->root = root;
}

void printTemp(BSTreeNode* root, string& result)
{
	;
}

string BSTree::printTree()
{
	if (root == NULL)
		return "\0";
	BSTreeNode* newroot = new BSTreeNode;
	newroot = root;
	stack<BSTreeNode*> q;
	while (!q.empty() || newroot)
	{
		while (newroot)
		{
			cout << newroot->getData() << " ";
			q.push(newroot);
			newroot = newroot->getLChild();
		}
		if (!q.empty())
		{
			newroot = q.top();
			q.pop();
			newroot = newroot->getRChild();
		}
	}
	return "\0";
}

bool BSTree::searchNode(int val) {
	BSTreeNode* newroot = new BSTreeNode;
	newroot = root;
	while (newroot != NULL)
	{
		if (newroot->getData() == val)
			return 1;
		else if(newroot->getData()>val)
			newroot = newroot->getLChild();
		
		else if (newroot->getData() < val)
			newroot = newroot->getRChild();
		
	}
	if (newroot == NULL)return 0;
}


bool BSTree::addNode(int val)
{
	BSTreeNode* k = new BSTreeNode;
		BSTreeNode* newroot = new BSTreeNode;
		newroot = root;
		while (newroot != NULL)
		{
			if (newroot->getData() > val)
			{
				k = newroot;
				newroot = newroot->getLChild();
			}
			else if (newroot->getData() < val)
			{
				k = newroot;
				newroot = newroot->getRChild();
			}
			else return 0;
		}
		if (k->getData() > val)
		{
			BSTreeNode* newroot2 = new BSTreeNode;
			newroot2->setData(val);
			k->setLChild(newroot2);
			return 1;
		}
		else
		{
			BSTreeNode* newroot2 = new BSTreeNode;
			newroot2->setData(val);
			k->setRChild(newroot2);
			return 1;
		}
}

bool BSTree::deleteNode(int val)
{
	BSTreeNode* k = new BSTreeNode;
	BSTreeNode* newroot = new BSTreeNode;
	newroot = root;
	k = newroot;
	while (newroot != NULL)
	{
		if (newroot->getData() == val)
		{
			if (newroot->getLChild() == NULL && newroot->getRChild() == NULL)
			{
				if (k->getData() > val)
				{
					delete newroot;
					k->setLChild(NULL);
					return 1;
				}
				else
				{
					delete newroot;
					k->setRChild(NULL);
					return 1;
				}
			}
			else if (newroot->getLChild() != NULL && newroot->getRChild() == NULL)
			{
				if (k->getData() > val)
				{
					k->setLChild(newroot->getLChild());
					delete newroot;
					return 1;
				}
				else
				{
					k->setRChild(newroot->getLChild());
					delete newroot;
					return 1;
				}
			}
			else if (newroot->getLChild() == NULL && newroot->getRChild() != NULL)
			{
				if (k->getData() > val)
				{
					k->setLChild(newroot->getRChild());
					delete newroot;
					return 1;
				}
				else
				{
					k->setRChild(newroot->getRChild());
					delete newroot;
					return 1;
				}
			}
			else if (newroot->getLChild() != NULL && newroot->getRChild() != NULL)
			{
				BSTreeNode* newroot2 = new BSTreeNode;
				newroot2 = newroot->getLChild();
				k = newroot;
				int count = 1;
				while (newroot2->getRChild() != NULL)
				{
					k = newroot2;
					newroot2 = newroot2->getRChild();
					count++;
				}
				newroot->setData(newroot2->getData());
				if (count == 1)
				{
					k->setLChild(NULL);
					return 1;
				}
				else
				{
					k->setRChild(NULL);
					delete newroot2;
					return 1;
				}
			}
		}
		else if (newroot->getData() > val)
		{
			k = newroot;
			newroot = newroot->getLChild();
		}
		else if (newroot->getData() < val)
		{
			k = newroot;
			newroot = newroot->getRChild();
		}
	}
	if (newroot == NULL)return 0;
}
